import java.util.Scanner;

/**
 * @author yu
 * @date 2025年04月17日 16:46
 *
 * 96. 不同的二叉搜索树 - 中
 * 给你一个整数 n ，
 * 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树
 * 有多少种？返回满足题意的二叉搜索树的种数。
 */
public class _09_dp_07numTrees {
    public static int numTrees(int n){
        int[] dp = new int[n+1];
        dp[0]=1;dp[1]=1;
        for(int i = 2; i <= n; i++){
            for(int j = 1;j<=i;j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(numTrees(n));
        scanner.close();
    }
}
